package com.hqq.leetcode.dp;

/**
 * BackPackV 背包问题5
 * Description:
 * Given n items with size nums[i] which an integer array and all positive numbers.
 * An integer target denotes the size of a backpack. Find the number of possible fill the backpack.
 * Each item may only be used once
 * Input:
 * [1,2,3,3,7],7
 * Output:
 * 2
 * <p>
 * Created by heqianqian on 2017/9/17.
 */
public class BackPackV {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 3, 7};
        BackPackV bp5 = new BackPackV();
        int max = bp5.backPackVI(nums, 7);
        System.out.println(max);
    }

    /*
    * @param nums: an integer array and all positive numbers, no duplicates
    * @param target: An integer
    * @return: An integer
    */
    public int backPackVI(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >= 0; j--) {
                if (j >= nums[i]) dp[j] += dp[j-nums[i]];
            }
        }
        return dp[target];
    }
}
